{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Overlap Similarity\n",
    "----\n",
    "\n",
    "In this notebook we will explore the Overlap Coefficient and compare it again Jaccard.  Similarity can be between neighboring vertices (default) or second hop neighbors\n",
    "\n",
    "\n",
    "Notebook Credits\n",
    "\n",
    "    Original Authors: Brad Rees\n",
    "    Created:   10/14/2019\n",
    "    Last Edit: 01/23/2020\n",
    "\n",
    "RAPIDS Versions: 0.12.0a\n",
    "\n",
    "Test Hardware\n",
    "* GV100 32G, CUDA 10.0\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction - Common Neighbor Similarity \n",
    "\n",
    "One of the most common types of vertex similarity is to evaluate the neighborhood of vertex pairs and looks at the number of common neighbors.  TThat type of similar comes from statistics and is based on set comparison.  Both Jaccard and the Overlap Coefficient operate on sets, and in a graph setting, those sets are the list of neighboring vertices. <br>\n",
    "For those that like math:  The neighbors of a vertex, _v_, is defined as the set, _U_, of vertices connected by way of an edge to vertex v, or _N(v) = {U} where v ∈ V and ∀ u ∈ U ∃ edge(v,u)∈ E_.\n",
    "\n",
    "For the rest of this introduction, set __A__ will equate to _A = N(i)_ and set __B__ will quate to _B = N(j)_.  That just make the rest of the text more readable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Overlap Coefficient"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Overlap Coefficient between two sets is defined as the ratio of the volume of their intersection divided by the volume of the smaller set.\n",
    "The Overlap Coefficient can be defined as\n",
    "\n",
    "<a href=\"https://www.codecogs.com/eqnedit.php?latex=oc(A,B)&space;=&space;\\frac{|A|&space;\\cap&space;|B|}{min(|A|,&space;|B|)&space;}\" target=\"_blank\"><img src=\"https://latex.codecogs.com/gif.latex?oc(A,B)&space;=&space;\\frac{|A&space;\\cap&space;B|}{min(|A|,&space;|B|)&space;}\" title=\"oc(A,B) = \\frac{|A \\cap B|}{min(|A|, |B|) }\" /></a>\n",
    "\n",
    "To compute the Overlap Coefficient between all pairs of vertices connected by an edge in cuGraph use: <br>\n",
    "\n",
    "__df = cugraph.overlap(G)__\n",
    "\n",
    "    G: A cugraph.Graph object\n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: cudf.DataFrame with three names columns:\n",
    "        df[\"source\"]: The source vertex id.\n",
    "        df[\"destination\"]: The destination vertex id.\n",
    "        df[\"overlap_coeff\"]: The overlap coefficient computed between the source and destination vertex.\n",
    "\n",
    "__References__\n",
    "- https://en.wikipedia.org/wiki/Overlap_coefficient\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Refresh on Jaccard\n",
    "The Jaccard similarity between two sets is defined as the ratio of the volume of their intersection divided by the volume of their union. \n",
    "\n",
    "The Jaccard Similarity can then be defined as\n",
    "\n",
    "<a href=\"https://www.codecogs.com/eqnedit.php?latex=js(A,B)&space;=&space;\\frac{|A&space;\\cap&space;B|}{|A&space;\\cup&space;B&space;|&space;}&space;=&space;\\frac{|A&space;\\cap&space;B|}{&space;|A|&space;&plus;&space;|B|&space;-&space;|A&space;\\cup&space;B&space;|&space;}\" target=\"_blank\"><img src=\"https://latex.codecogs.com/gif.latex?js(A,B)&space;=&space;\\frac{|A&space;\\cap&space;B|}{|A&space;\\cup&space;B&space;|&space;}&space;=&space;\\frac{|A&space;\\cap&space;B|}{&space;|A|&space;&plus;&space;|B|&space;-&space;|A&space;\\cup&space;B&space;|&space;}\" title=\"js(A,B) = \\frac{|A \\cap B|}{|A \\cup B | } = \\frac{|A \\cap B|}{ |A| + |B| - |A \\cup B | }\" /></a>\n",
    "\n",
    "\n",
    "To compute the Jaccard similarity between all pairs of vertices connected by an edge in cuGraph use: <br>\n",
    "__df = cugraph.jaccard(G)__\n",
    "\n",
    "    G: A cugraph.Graph object\n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: cudf.DataFrame with three names columns:\n",
    "        df[\"source\"]: The source vertex id.\n",
    "        df[\"destination\"]: The destination vertex id.\n",
    "        df[\"jaccard_coeff\"]: The jaccard coefficient computed between the source and destination vertex.\n",
    "<br>\n",
    "\n",
    "See the Jaccard notebook for additional information and background"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Additional Reading\n",
    "- [Similarity in graphs: Jaccard versus the Overlap Coefficient](https://medium.com/rapids-ai/similarity-in-graphs-jaccard-versus-the-overlap-coefficient-610e083b877d)\n",
    "- [Wikipedia: Overlap Coefficient](https://en.wikipedia.org/wiki/Overlap_coefficient)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### cuGraph Notice \n",
    "The current version of cuGraph has some limitations:\n",
    "\n",
    "* Vertex IDs need to be 32-bit integers.\n",
    "* Vertex IDs are expected to be contiguous integers starting from 0.\n",
    "\n",
    "cuGraph provides the renumber function to mitigate this problem. Input vertex IDs for the renumber function can be either 32-bit or 64-bit integers, can be non-contiguous, and can start from an arbitrary number. The renumber function maps the provided input vertex IDs to 32-bit contiguous integers starting from 0. cuGraph still requires the renumbered vertex IDs to be representable in 32-bit integers. These limitations are being addressed and will be fixed soon."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Data\n",
    "We will be using the Zachary Karate club dataset \n",
    "*W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of\n",
    "Anthropological Research 33, 452-473 (1977).*\n",
    "\n",
    "\n",
    "![Karate Club](../img/zachary_black_lines.png)\n",
    "\n",
    "This is a small graph which allows for easy visual inspection to validate results.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Let's get started!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "from collections import OrderedDict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Define some Print functions\n",
    "(the `del` are not needed since going out of scope should free memory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing the top most similar vertices\n",
    "def print_most_similar_jaccard(df):\n",
    "    \n",
    "    jmax = df['jaccard_coeff'].max()\n",
    "    dm = df.query('jaccard_coeff >= @jmax')    \n",
    "    \n",
    "    #find the best\n",
    "    for i in range(len(dm)):    \n",
    "        print(\"Vertices \" + str(dm['source'][i]) + \" and \" + \n",
    "              str(dm['destination'][i]) + \" are most similar with score: \" \n",
    "              + str(dm['jaccard_coeff'][i]))\n",
    "    del jmax\n",
    "    del dm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing the top most similar vertices\n",
    "def print_most_similar_overlap(df):\n",
    "    \n",
    "    smax = df['overlap_coeff'].max()\n",
    "    dm = df.query('overlap_coeff >= @smax and source < destination')      \n",
    "    \n",
    "    for i in range(len(dm)):\n",
    "        print(\"Vertices \" + str(dm['source'][i]) + \" and \" + \n",
    "          str(dm['destination'][i]) + \" are most similar with score: \" \n",
    "          + str(dm['overlap_coeff'][i]))\n",
    "        \n",
    "    del smax\n",
    "    del dm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing jaccard similar vertices based on a threshold\n",
    "def print_jaccard_threshold(_d, limit):\n",
    "    \n",
    "    filtered = _d.query('jaccard_coeff > @limit')\n",
    "    \n",
    "    for i in range(len(filtered)):\n",
    "        print(\"Vertices \" + str(filtered['source'][i]) + \" and \" + \n",
    "            str(filtered['destination'][i]) + \" are similar with score: \" + \n",
    "            str(filtered['jaccard_coeff'][i]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing similar vertices based on a threshold\n",
    "def print_overlap_threshold(_d, limit):\n",
    "    \n",
    "    filtered = _d.query('overlap_coeff > @limit')\n",
    "    \n",
    "    for i in range(len(filtered)):\n",
    "        if filtered['source'][i] != filtered['destination'][i] :\n",
    "            print(\"Vertices \" + str(filtered['source'][i]) + \" and \" + \n",
    "                str(filtered['destination'][i]) + \" are similar with score: \" + \n",
    "                str(filtered['overlap_coeff'][i]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read the CSV datafile using cuDF\n",
    "data file is actually _tab_ separated, so we need to set the delimiter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test file  \n",
    "datafile='../data/karate-data.csv'\n",
    "\n",
    "gdf = cudf.read_csv(datafile, delimiter='\\t', names=['src', 'dst'], dtype=['int32', 'int32'] )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(156, 2)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Let's look at the DataFrame. There should be two columns and 156 records\n",
    "gdf.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>src</th>\n",
       "      <th>dst</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   src  dst\n",
       "0    1    2\n",
       "1    1    3\n",
       "2    1    4\n",
       "3    1    5\n",
       "4    1    6"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Look at the first few data records - the output should be two colums src and dst\n",
    "gdf.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph \n",
    "G = cugraph.Graph()\n",
    "G.from_cudf_edgelist(gdf, source='src', destination='dst')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "34"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How many vertices are in the graph?  Remember that Graph is zero based\n",
    "G.number_of_vertices()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_The test graph has only 34 vertices, so why is the Graph listing 35?_\n",
    "\n",
    "As mentioned above, cuGraph vertex numbering is zero-based, meaning that the first vertex ID starts at zero.  The test dataset is 1-based.  Because of that, the Graph object adds an extra isolated vertex with an ID of zero.  Hence the difference in vertex count.  \n",
    "We could have run _renumbering_ on the data, or updated the value of each element _gdf['src'] = gdf['src'] - 1_    \n",
    "for now, we will just state that vertex 0 is not part of the dataset and can be ignored"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "--- \n",
    "# Jaccard "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 25.4 ms, sys: 896 µs, total: 26.3 ms\n",
      "Wall time: 24.5 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "# Call cugraph.nvJaccard \n",
    "jdf = cugraph.jaccard(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 33 and 34 are most similar with score: 0.5263158\n",
      "Vertices 34 and 33 are most similar with score: 0.5263158\n"
     ]
    }
   ],
   "source": [
    "# Which two vertices are the most similar?\n",
    "print_most_similar_jaccard(jdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Most similar shoul be 33 and 34.\n",
    "Vertex 33 has 12 neighbors, vertex 34 has 17 neighbors.  They share 10 neighbors in common:\n",
    "$jaccard = 10 / (10 + (12 -10) + (17-10)) = 10 / 19 = 0.526$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 4 and 8 are similar with score: 0.42857143\n",
      "Vertices 8 and 4 are similar with score: 0.42857143\n",
      "Vertices 33 and 34 are similar with score: 0.5263158\n",
      "Vertices 34 and 33 are similar with score: 0.5263158\n"
     ]
    }
   ],
   "source": [
    "### let's look at all similarities over a threshold\n",
    "print_jaccard_threshold(jdf, 0.4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 33 and 34 are similar with score: 0.5263158\n",
      "Vertices 4 and 8 are similar with score: 0.42857143\n",
      "Vertices 1 and 2 are similar with score: 0.3888889\n",
      "Vertices 4 and 14 are similar with score: 0.375\n",
      "Vertices 2 and 4 are similar with score: 0.36363637\n",
      "Vertices 3 and 4 are similar with score: 0.33333334\n",
      "Vertices 6 and 7 are similar with score: 0.33333334\n",
      "Vertices 2 and 8 are similar with score: 0.3\n",
      "Vertices 1 and 4 are similar with score: 0.29411766\n",
      "Vertices 9 and 31 are similar with score: 0.2857143\n",
      "Vertices 24 and 30 are similar with score: 0.2857143\n",
      "Vertices 2 and 14 are similar with score: 0.27272728\n",
      "Vertices 3 and 8 are similar with score: 0.27272728\n",
      "Vertices 2 and 3 are similar with score: 0.26666668\n",
      "Vertices 3 and 14 are similar with score: 0.25\n",
      "Vertices 1 and 3 are similar with score: 0.23809524\n",
      "Vertices 9 and 33 are similar with score: 0.21428572\n",
      "Vertices 5 and 11 are similar with score: 0.2\n",
      "Vertices 6 and 17 are similar with score: 0.2\n",
      "Vertices 7 and 17 are similar with score: 0.2\n",
      "Vertices 25 and 26 are similar with score: 0.2\n",
      "Vertices 27 and 30 are similar with score: 0.2\n",
      "Vertices 1 and 8 are similar with score: 0.1764706\n",
      "Vertices 1 and 14 are similar with score: 0.16666667\n",
      "Vertices 5 and 7 are similar with score: 0.16666667\n",
      "Vertices 6 and 11 are similar with score: 0.16666667\n",
      "Vertices 30 and 34 are similar with score: 0.16666667\n",
      "Vertices 24 and 34 are similar with score: 0.15789473\n",
      "Vertices 3 and 9 are similar with score: 0.15384616\n",
      "Vertices 4 and 13 are similar with score: 0.14285715\n",
      "Vertices 30 and 33 are similar with score: 0.14285715\n",
      "Vertices 31 and 33 are similar with score: 0.14285715\n",
      "Vertices 24 and 33 are similar with score: 0.13333334\n",
      "Vertices 24 and 28 are similar with score: 0.125\n",
      "Vertices 25 and 32 are similar with score: 0.125\n",
      "Vertices 26 and 32 are similar with score: 0.125\n",
      "Vertices 29 and 32 are similar with score: 0.125\n",
      "Vertices 1 and 5 are similar with score: 0.11764706\n",
      "Vertices 1 and 11 are similar with score: 0.11764706\n",
      "Vertices 1 and 6 are similar with score: 0.11111111\n",
      "Vertices 1 and 7 are similar with score: 0.11111111\n",
      "Vertices 31 and 34 are similar with score: 0.10526316\n",
      "Vertices 2 and 18 are similar with score: 0.1\n",
      "Vertices 2 and 22 are similar with score: 0.1\n",
      "Vertices 9 and 34 are similar with score: 0.1\n",
      "Vertices 32 and 34 are similar with score: 0.0952381\n",
      "Vertices 2 and 20 are similar with score: 0.09090909\n",
      "Vertices 15 and 33 are similar with score: 0.07692308\n",
      "Vertices 16 and 33 are similar with score: 0.07692308\n",
      "Vertices 19 and 33 are similar with score: 0.07692308\n",
      "Vertices 21 and 33 are similar with score: 0.07692308\n",
      "Vertices 23 and 33 are similar with score: 0.07692308\n",
      "Vertices 1 and 13 are similar with score: 0.05882353\n",
      "Vertices 1 and 18 are similar with score: 0.05882353\n",
      "Vertices 1 and 22 are similar with score: 0.05882353\n",
      "Vertices 32 and 33 are similar with score: 0.05882353\n",
      "Vertices 1 and 20 are similar with score: 0.055555556\n",
      "Vertices 15 and 34 are similar with score: 0.055555556\n",
      "Vertices 16 and 34 are similar with score: 0.055555556\n",
      "Vertices 19 and 34 are similar with score: 0.055555556\n",
      "Vertices 21 and 34 are similar with score: 0.055555556\n",
      "Vertices 23 and 34 are similar with score: 0.055555556\n",
      "Vertices 27 and 34 are similar with score: 0.055555556\n",
      "Vertices 29 and 34 are similar with score: 0.05263158\n",
      "Vertices 1 and 9 are similar with score: 0.05\n",
      "Vertices 28 and 34 are similar with score: 0.05\n",
      "Vertices 3 and 33 are similar with score: 0.04761905\n"
     ]
    }
   ],
   "source": [
    "# Since it is a small graph we can print all scores, notice that only vertices that are neighbors are being compared\n",
    "#\n",
    "# Before printing, let's get rid of the duplicates (x compared to y is the same as y compared to x).  We will do that\n",
    "# by performing a query.  Then let's sort the data by score\n",
    "\n",
    "jdf_s = jdf.query('source < destination').sort_values(by='jaccard_coeff', ascending=False)\n",
    "\n",
    "print_jaccard_threshold(jdf_s, 0.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Overlap Coefficient"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Noticed that the Jaccard score is based on the number of common items over the combined (union) set of items.  That makes sense when the two sets being compared are relativcely close in size.  However, when one set is considerable larger, then it is important to know if one set is a proper subset of the other <br>\n",
    "See:  [Similarity in graphs: Jaccard versus the Overlap Coefficient](https://medium.com/rapids-ai/similarity-in-graphs-jaccard-versus-the-overlap-coefficient-610e083b877d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 23.1 ms, sys: 1.46 ms, total: 24.5 ms\n",
      "Wall time: 29.6 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "# Call cugraph.nvJaccard \n",
    "odf = cugraph.overlap(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 1 and 4 are most similar with score: 0.8333333\n",
      "Vertices 33 and 34 are most similar with score: 0.8333333\n"
     ]
    }
   ],
   "source": [
    "# print the top similar pair - this function include code to drop duplicates  \n",
    "print_most_similar_overlap(odf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 1 and 4 are similar with score: 0.8333333\n",
      "Vertices 33 and 34 are similar with score: 0.8333333\n",
      "Vertices 1 and 2 are similar with score: 0.7777778\n",
      "Vertices 1 and 8 are similar with score: 0.75\n",
      "Vertices 2 and 8 are similar with score: 0.75\n",
      "Vertices 3 and 8 are similar with score: 0.75\n",
      "Vertices 4 and 8 are similar with score: 0.75\n",
      "Vertices 30 and 34 are similar with score: 0.75\n",
      "Vertices 1 and 5 are similar with score: 0.6666667\n",
      "Vertices 1 and 11 are similar with score: 0.6666667\n",
      "Vertices 2 and 4 are similar with score: 0.6666667\n",
      "Vertices 3 and 4 are similar with score: 0.6666667\n",
      "Vertices 1 and 14 are similar with score: 0.6\n",
      "Vertices 2 and 14 are similar with score: 0.6\n",
      "Vertices 3 and 14 are similar with score: 0.6\n",
      "Vertices 4 and 14 are similar with score: 0.6\n",
      "Vertices 9 and 33 are similar with score: 0.6\n",
      "Vertices 24 and 34 are similar with score: 0.6\n"
     ]
    }
   ],
   "source": [
    "# print all similarities over a threshold, in this case 0.5\n",
    "#also, drop duplicates\n",
    "odf_s = odf.query('source < destination').sort_values(by='overlap_coeff', ascending=False)\n",
    "\n",
    "print_overlap_threshold(odf_s, 0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Expanding similarity scoring to 2-hop vertex pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get all two-hop vertex pairs\n",
    "p = G.get_two_hop_neighbors()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's look at the Jaccard score\n",
    "ol2 = cugraph.overlap(G, vertex_pair=p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 1 and 4 are most similar with score: 0.8333333\n",
      "Vertices 33 and 34 are most similar with score: 0.8333333\n"
     ]
    }
   ],
   "source": [
    "print_most_similar_overlap(odf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 5 and 6 are similar with score: 1.0\n",
      "Vertices 5 and 12 are similar with score: 1.0\n",
      "Vertices 6 and 12 are similar with score: 1.0\n",
      "Vertices 12 and 13 are similar with score: 1.0\n",
      "Vertices 12 and 14 are similar with score: 1.0\n",
      "Vertices 12 and 18 are similar with score: 1.0\n",
      "Vertices 12 and 20 are similar with score: 1.0\n",
      "Vertices 12 and 22 are similar with score: 1.0\n",
      "Vertices 12 and 32 are similar with score: 1.0\n",
      "Vertices 7 and 11 are similar with score: 1.0\n",
      "Vertices 7 and 12 are similar with score: 1.0\n",
      "Vertices 8 and 12 are similar with score: 1.0\n",
      "Vertices 8 and 13 are similar with score: 1.0\n",
      "Vertices 8 and 14 are similar with score: 1.0\n",
      "Vertices 8 and 18 are similar with score: 1.0\n",
      "Vertices 8 and 22 are similar with score: 1.0\n",
      "Vertices 29 and 33 are similar with score: 1.0\n",
      "Vertices 10 and 14 are similar with score: 1.0\n",
      "Vertices 10 and 28 are similar with score: 1.0\n",
      "Vertices 10 and 29 are similar with score: 1.0\n",
      "Vertices 10 and 33 are similar with score: 1.0\n",
      "Vertices 9 and 10 are similar with score: 1.0\n",
      "Vertices 9 and 12 are similar with score: 1.0\n",
      "Vertices 9 and 15 are similar with score: 1.0\n",
      "Vertices 9 and 16 are similar with score: 1.0\n",
      "Vertices 9 and 19 are similar with score: 1.0\n",
      "Vertices 9 and 21 are similar with score: 1.0\n",
      "Vertices 9 and 23 are similar with score: 1.0\n",
      "Vertices 11 and 12 are similar with score: 1.0\n",
      "Vertices 23 and 24 are similar with score: 1.0\n",
      "Vertices 23 and 30 are similar with score: 1.0\n",
      "Vertices 23 and 31 are similar with score: 1.0\n",
      "Vertices 23 and 32 are similar with score: 1.0\n",
      "Vertices 15 and 16 are similar with score: 1.0\n",
      "Vertices 15 and 19 are similar with score: 1.0\n",
      "Vertices 15 and 21 are similar with score: 1.0\n",
      "Vertices 15 and 23 are similar with score: 1.0\n",
      "Vertices 15 and 24 are similar with score: 1.0\n",
      "Vertices 15 and 30 are similar with score: 1.0\n",
      "Vertices 15 and 31 are similar with score: 1.0\n",
      "Vertices 15 and 32 are similar with score: 1.0\n",
      "Vertices 16 and 19 are similar with score: 1.0\n",
      "Vertices 16 and 21 are similar with score: 1.0\n",
      "Vertices 16 and 23 are similar with score: 1.0\n",
      "Vertices 16 and 24 are similar with score: 1.0\n",
      "Vertices 20 and 22 are similar with score: 1.0\n",
      "Vertices 21 and 23 are similar with score: 1.0\n",
      "Vertices 21 and 24 are similar with score: 1.0\n",
      "Vertices 21 and 30 are similar with score: 1.0\n",
      "Vertices 21 and 31 are similar with score: 1.0\n",
      "Vertices 21 and 32 are similar with score: 1.0\n",
      "Vertices 27 and 33 are similar with score: 1.0\n",
      "Vertices 24 and 27 are similar with score: 1.0\n",
      "Vertices 1 and 17 are similar with score: 1.0\n",
      "Vertices 19 and 21 are similar with score: 1.0\n",
      "Vertices 19 and 23 are similar with score: 1.0\n",
      "Vertices 19 and 24 are similar with score: 1.0\n",
      "Vertices 19 and 30 are similar with score: 1.0\n",
      "Vertices 19 and 31 are similar with score: 1.0\n",
      "Vertices 19 and 32 are similar with score: 1.0\n",
      "Vertices 16 and 30 are similar with score: 1.0\n",
      "Vertices 16 and 31 are similar with score: 1.0\n",
      "Vertices 16 and 32 are similar with score: 1.0\n",
      "Vertices 18 and 20 are similar with score: 1.0\n",
      "Vertices 18 and 22 are similar with score: 1.0\n",
      "Vertices 13 and 14 are similar with score: 1.0\n",
      "Vertices 14 and 18 are similar with score: 1.0\n",
      "Vertices 14 and 20 are similar with score: 1.0\n",
      "Vertices 14 and 22 are similar with score: 1.0\n",
      "Vertices 2 and 12 are similar with score: 1.0\n",
      "Vertices 2 and 13 are similar with score: 1.0\n",
      "Vertices 3 and 12 are similar with score: 1.0\n",
      "Vertices 3 and 13 are similar with score: 1.0\n",
      "Vertices 3 and 18 are similar with score: 1.0\n",
      "Vertices 3 and 22 are similar with score: 1.0\n",
      "Vertices 4 and 12 are similar with score: 1.0\n",
      "Vertices 4 and 18 are similar with score: 1.0\n",
      "Vertices 4 and 22 are similar with score: 1.0\n",
      "Vertices 33 and 34 are similar with score: 0.8333333\n",
      "Vertices 1 and 4 are similar with score: 0.8333333\n",
      "Vertices 1 and 2 are similar with score: 0.7777778\n",
      "Vertices 30 and 34 are similar with score: 0.75\n",
      "Vertices 28 and 33 are similar with score: 0.75\n",
      "Vertices 1 and 8 are similar with score: 0.75\n",
      "Vertices 2 and 8 are similar with score: 0.75\n",
      "Vertices 3 and 8 are similar with score: 0.75\n",
      "Vertices 3 and 31 are similar with score: 0.75\n",
      "Vertices 4 and 8 are similar with score: 0.75\n"
     ]
    }
   ],
   "source": [
    "# print all similarities over a threshold, in this case 0.5\n",
    "#also, drop duplicates\n",
    "odf_s2 = ol2.query('source < destination').sort_values(by='overlap_coeff', ascending=False)\n",
    "\n",
    "print_overlap_threshold(odf_s2, 0.74)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Let's now compare the Overlap Coefficient with the Jaccard Similarity "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.nvJaccard \n",
    "jdf = cugraph.jaccard(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 33 and 34 are most similar with score: 0.5263158\n",
      "Vertices 34 and 33 are most similar with score: 0.5263158\n"
     ]
    }
   ],
   "source": [
    "# Which two vertices are the most similar?\n",
    "print_most_similar_jaccard(jdf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's combine the Jaccard and Overlap scores\n",
    "mdf = jdf.merge(odf, on=['source','destination'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Also want to include the vertex degree\n",
    "degree = G.degree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "dS = degree.rename(columns={'vertex':'source','degree': 'src_degree'})\n",
    "dD = degree.rename(columns={'vertex':'destination','degree': 'dst_degree'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = mdf.merge(dS, how=\"left\", on='source')\n",
    "m = m.merge(dD, how=\"left\", on='destination')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>source</th>\n",
       "      <th>destination</th>\n",
       "      <th>jaccard_coeff</th>\n",
       "      <th>overlap_coeff</th>\n",
       "      <th>src_degree</th>\n",
       "      <th>dst_degree</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>102</th>\n",
       "      <td>33</td>\n",
       "      <td>34</td>\n",
       "      <td>0.526316</td>\n",
       "      <td>0.833333</td>\n",
       "      <td>24</td>\n",
       "      <td>34</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>66</th>\n",
       "      <td>4</td>\n",
       "      <td>8</td>\n",
       "      <td>0.428571</td>\n",
       "      <td>0.750000</td>\n",
       "      <td>12</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>32</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>0.388889</td>\n",
       "      <td>0.777778</td>\n",
       "      <td>32</td>\n",
       "      <td>18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>68</th>\n",
       "      <td>4</td>\n",
       "      <td>14</td>\n",
       "      <td>0.375000</td>\n",
       "      <td>0.600000</td>\n",
       "      <td>12</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>50</th>\n",
       "      <td>2</td>\n",
       "      <td>4</td>\n",
       "      <td>0.363636</td>\n",
       "      <td>0.666667</td>\n",
       "      <td>18</td>\n",
       "      <td>12</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>59</th>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>0.333333</td>\n",
       "      <td>0.666667</td>\n",
       "      <td>20</td>\n",
       "      <td>12</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>73</th>\n",
       "      <td>6</td>\n",
       "      <td>7</td>\n",
       "      <td>0.333333</td>\n",
       "      <td>0.500000</td>\n",
       "      <td>8</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>51</th>\n",
       "      <td>2</td>\n",
       "      <td>8</td>\n",
       "      <td>0.300000</td>\n",
       "      <td>0.750000</td>\n",
       "      <td>18</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>34</th>\n",
       "      <td>1</td>\n",
       "      <td>4</td>\n",
       "      <td>0.294118</td>\n",
       "      <td>0.833333</td>\n",
       "      <td>32</td>\n",
       "      <td>12</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>27</th>\n",
       "      <td>24</td>\n",
       "      <td>30</td>\n",
       "      <td>0.285714</td>\n",
       "      <td>0.500000</td>\n",
       "      <td>10</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>86</th>\n",
       "      <td>9</td>\n",
       "      <td>31</td>\n",
       "      <td>0.285714</td>\n",
       "      <td>0.500000</td>\n",
       "      <td>10</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>52</th>\n",
       "      <td>2</td>\n",
       "      <td>14</td>\n",
       "      <td>0.272727</td>\n",
       "      <td>0.600000</td>\n",
       "      <td>18</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>60</th>\n",
       "      <td>3</td>\n",
       "      <td>8</td>\n",
       "      <td>0.272727</td>\n",
       "      <td>0.750000</td>\n",
       "      <td>20</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>49</th>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>0.266667</td>\n",
       "      <td>0.444444</td>\n",
       "      <td>18</td>\n",
       "      <td>20</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>63</th>\n",
       "      <td>3</td>\n",
       "      <td>14</td>\n",
       "      <td>0.250000</td>\n",
       "      <td>0.600000</td>\n",
       "      <td>20</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>33</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>0.238095</td>\n",
       "      <td>0.500000</td>\n",
       "      <td>32</td>\n",
       "      <td>20</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>87</th>\n",
       "      <td>9</td>\n",
       "      <td>33</td>\n",
       "      <td>0.214286</td>\n",
       "      <td>0.600000</td>\n",
       "      <td>10</td>\n",
       "      <td>24</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>71</th>\n",
       "      <td>5</td>\n",
       "      <td>11</td>\n",
       "      <td>0.200000</td>\n",
       "      <td>0.333333</td>\n",
       "      <td>6</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>75</th>\n",
       "      <td>6</td>\n",
       "      <td>17</td>\n",
       "      <td>0.200000</td>\n",
       "      <td>0.500000</td>\n",
       "      <td>8</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>79</th>\n",
       "      <td>7</td>\n",
       "      <td>17</td>\n",
       "      <td>0.200000</td>\n",
       "      <td>0.500000</td>\n",
       "      <td>8</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     source  destination  jaccard_coeff  overlap_coeff  src_degree  dst_degree\n",
       "102      33           34       0.526316       0.833333          24          34\n",
       "66        4            8       0.428571       0.750000          12           8\n",
       "32        1            2       0.388889       0.777778          32          18\n",
       "68        4           14       0.375000       0.600000          12          10\n",
       "50        2            4       0.363636       0.666667          18          12\n",
       "59        3            4       0.333333       0.666667          20          12\n",
       "73        6            7       0.333333       0.500000           8           8\n",
       "51        2            8       0.300000       0.750000          18           8\n",
       "34        1            4       0.294118       0.833333          32          12\n",
       "27       24           30       0.285714       0.500000          10           8\n",
       "86        9           31       0.285714       0.500000          10           8\n",
       "52        2           14       0.272727       0.600000          18          10\n",
       "60        3            8       0.272727       0.750000          20           8\n",
       "49        2            3       0.266667       0.444444          18          20\n",
       "63        3           14       0.250000       0.600000          20          10\n",
       "33        1            3       0.238095       0.500000          32          20\n",
       "87        9           33       0.214286       0.600000          10          24\n",
       "71        5           11       0.200000       0.333333           6           6\n",
       "75        6           17       0.200000       0.500000           8           4\n",
       "79        7           17       0.200000       0.500000           8           4"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m.query('source < destination').sort_values(by='jaccard_coeff', ascending=False).head(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>source</th>\n",
       "      <th>destination</th>\n",
       "      <th>jaccard_coeff</th>\n",
       "      <th>overlap_coeff</th>\n",
       "      <th>src_degree</th>\n",
       "      <th>dst_degree</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>34</th>\n",
       "      <td>1</td>\n",
       "      <td>4</td>\n",
       "      <td>0.294118</td>\n",
       "      <td>0.833333</td>\n",
       "      <td>32</td>\n",
       "      <td>12</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>102</th>\n",
       "      <td>33</td>\n",
       "      <td>34</td>\n",
       "      <td>0.526316</td>\n",
       "      <td>0.833333</td>\n",
       "      <td>24</td>\n",
       "      <td>34</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>32</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>0.388889</td>\n",
       "      <td>0.777778</td>\n",
       "      <td>32</td>\n",
       "      <td>18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>38</th>\n",
       "      <td>1</td>\n",
       "      <td>8</td>\n",
       "      <td>0.176471</td>\n",
       "      <td>0.750000</td>\n",
       "      <td>32</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>51</th>\n",
       "      <td>2</td>\n",
       "      <td>8</td>\n",
       "      <td>0.300000</td>\n",
       "      <td>0.750000</td>\n",
       "      <td>18</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>60</th>\n",
       "      <td>3</td>\n",
       "      <td>8</td>\n",
       "      <td>0.272727</td>\n",
       "      <td>0.750000</td>\n",
       "      <td>20</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>66</th>\n",
       "      <td>4</td>\n",
       "      <td>8</td>\n",
       "      <td>0.428571</td>\n",
       "      <td>0.750000</td>\n",
       "      <td>12</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>144</th>\n",
       "      <td>30</td>\n",
       "      <td>34</td>\n",
       "      <td>0.166667</td>\n",
       "      <td>0.750000</td>\n",
       "      <td>8</td>\n",
       "      <td>34</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>35</th>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>0.117647</td>\n",
       "      <td>0.666667</td>\n",
       "      <td>32</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>40</th>\n",
       "      <td>1</td>\n",
       "      <td>11</td>\n",
       "      <td>0.117647</td>\n",
       "      <td>0.666667</td>\n",
       "      <td>32</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>50</th>\n",
       "      <td>2</td>\n",
       "      <td>4</td>\n",
       "      <td>0.363636</td>\n",
       "      <td>0.666667</td>\n",
       "      <td>18</td>\n",
       "      <td>12</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>59</th>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>0.333333</td>\n",
       "      <td>0.666667</td>\n",
       "      <td>20</td>\n",
       "      <td>12</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>43</th>\n",
       "      <td>1</td>\n",
       "      <td>14</td>\n",
       "      <td>0.166667</td>\n",
       "      <td>0.600000</td>\n",
       "      <td>32</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>52</th>\n",
       "      <td>2</td>\n",
       "      <td>14</td>\n",
       "      <td>0.272727</td>\n",
       "      <td>0.600000</td>\n",
       "      <td>18</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>63</th>\n",
       "      <td>3</td>\n",
       "      <td>14</td>\n",
       "      <td>0.250000</td>\n",
       "      <td>0.600000</td>\n",
       "      <td>20</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>68</th>\n",
       "      <td>4</td>\n",
       "      <td>14</td>\n",
       "      <td>0.375000</td>\n",
       "      <td>0.600000</td>\n",
       "      <td>12</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>87</th>\n",
       "      <td>9</td>\n",
       "      <td>33</td>\n",
       "      <td>0.214286</td>\n",
       "      <td>0.600000</td>\n",
       "      <td>10</td>\n",
       "      <td>24</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>125</th>\n",
       "      <td>24</td>\n",
       "      <td>34</td>\n",
       "      <td>0.157895</td>\n",
       "      <td>0.600000</td>\n",
       "      <td>10</td>\n",
       "      <td>34</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>15</td>\n",
       "      <td>33</td>\n",
       "      <td>0.076923</td>\n",
       "      <td>0.500000</td>\n",
       "      <td>4</td>\n",
       "      <td>24</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>15</td>\n",
       "      <td>34</td>\n",
       "      <td>0.055556</td>\n",
       "      <td>0.500000</td>\n",
       "      <td>4</td>\n",
       "      <td>34</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     source  destination  jaccard_coeff  overlap_coeff  src_degree  dst_degree\n",
       "34        1            4       0.294118       0.833333          32          12\n",
       "102      33           34       0.526316       0.833333          24          34\n",
       "32        1            2       0.388889       0.777778          32          18\n",
       "38        1            8       0.176471       0.750000          32           8\n",
       "51        2            8       0.300000       0.750000          18           8\n",
       "60        3            8       0.272727       0.750000          20           8\n",
       "66        4            8       0.428571       0.750000          12           8\n",
       "144      30           34       0.166667       0.750000           8          34\n",
       "35        1            5       0.117647       0.666667          32           6\n",
       "40        1           11       0.117647       0.666667          32           6\n",
       "50        2            4       0.363636       0.666667          18          12\n",
       "59        3            4       0.333333       0.666667          20          12\n",
       "43        1           14       0.166667       0.600000          32          10\n",
       "52        2           14       0.272727       0.600000          18          10\n",
       "63        3           14       0.250000       0.600000          20          10\n",
       "68        4           14       0.375000       0.600000          12          10\n",
       "87        9           33       0.214286       0.600000          10          24\n",
       "125      24           34       0.157895       0.600000          10          34\n",
       "6        15           33       0.076923       0.500000           4          24\n",
       "7        15           34       0.055556       0.500000           4          34"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Now sort on the overlap\n",
    "m.query('source < destination').sort_values(by='overlap_coeff', ascending=False).head(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019, NVIDIA CORPORATION.\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\");  you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
    "___"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
